package Text16;

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n-- > 0) {
            int x = scanner.nextInt();
            int res = x;
            for (int i = 2; i <= x / i; i++) {
                if (x % i == 0) {
                    res = res / i * (i - 1);
                    while (x % i == 0) {
                        x /= i;
                    }
                }
            }
            if(x>1){
                res = res / x* (x - 1);
            }
            System.out.println(res);
        }
    }
}
